Phân tích

Với giải thuật đã mô tả ta dễ dàng thực hiện trực tiếp trên các đồ thị kích thước nhỏ,để có thể mã hóa và cài đặt hiệu quả cần đưa thêm các cấu trúc dữ liệu để sử dụng trong giải thuật.

Dữ liệu

• Hàm d(u) dùng để lưu trữ độ dài đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh u. Rõ ràng d(s)= 0. Ký hiệu X − ( u ) {\displaystyle X^{-}(u)} là tập tất cả các đỉnh có cạnh đi tới đỉnh u. Nếu với mọi v ∈ X − ( u ) {\displaystyle v\in X^{-}(u)} đã xác định được d(v) thì:

d ( u ) = m i n { d ( v ) + w ( v , u ) , v ∈ X − ( u ) } {\displaystyle d(u)=min\{d(v)+w(v,u),v\in X^{-}(u)\}}

.

• Để tính được giá trị nhỏ nhất này, như thông thường khi khởi tạo ta phải gán cho d(v)= ∞ {\displaystyle \infty } , sau đó gặp giá trị nhỏ hơn thì thay thế lại.
• Những đỉnh đã tính được d(v)hữu hạn được cho vào một hàng đợi có ưu tiên. Hàng đợi này luôn được bổ sung và sắp xếp lại nên một cấu trúc hợp lý là cấu trúc đống nhị phân (heap)...
• Để theo dõi trạng thái của các đỉnh trong quá trình xét, ta dùng hàm COLOR(u) xác định với mọi v ∈ V {\displaystyle v\in V} . Lúc đầu các đỉnh được tô màu trắng (WHITE), khi cho vào hàng đợi nó được tô màu xám (GRAY), khi đã tính xong khoảng cách nó được tô màu đen(BLACK).
• Nếu cần ghi lại đường đi ta sẽ phải dùng một hàm con trỏ PRE(u) để chỉ đỉnh đứng ngay trước đỉnh u trên đường đi ngắn nhất từ s tới u.